//给你一个非负整数数组 nums ，你最初位于数组的第一个位置。 
//
// 数组中的每个元素代表你在该位置可以跳跃的最大长度。 
//
// 你的目标是使用最少的跳跃次数到达数组的最后一个位置。 
//
// 假设你总是可以到达数组的最后一个位置。 
//
// 
//
// 示例 1: 
//
// 
//输入: nums = [2,3,1,1,4]
//输出: 2
//解释: 跳到最后一个位置的最小跳跃数是 2。
//     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
// 
//
// 示例 2: 
//
// 
//输入: nums = [2,3,0,1,4]
//输出: 2
// 
//
// 
//
// 提示: 
//
// 
// 1 <= nums.length <= 10⁴ 
// 0 <= nums[i] <= 1000 
// 
// Related Topics 贪心 数组 动态规划 👍 1653 👎 0


package leetcode.editor.cn;

/**
 * 跳跃游戏 II
 * @date 2022-06-10 09:37:37
 */
class P45_JumpGameIi{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 Solution solution = new P45_JumpGameIi().new Solution();
		  int[] a = new int[]{2,3,1,1,4};
		  int res = solution.jump(a);
		 System.out.println(res);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //https://leetcode.cn/problems/jump-game-ii/solution/45-by-ikaruga/
    public int jump(int[] nums) {
		if(nums == null){
			return 0;
		}
		int k = 0;//记录能够跳跃的最大距离
		int boder = 0;//每次跳跃的边界值
		int step = 0;//记录跳跃次数
		for (int i = 0; i < nums.length -1; i++) {
			// 继续往下遍历，统计边界范围内，哪一格能跳得更远，每走一步就更新一次能跳跃的最远位置下标
			// 其实就是在统计下一步的最优情况
			int temp = i + nums[i];
			k = Math.max(k,temp);
			// 如果到达了边界，那么一定要跳了，下一跳的边界下标就是之前统计的最优情况k，并且步数加1
			if(i == boder){
				step++;
				boder = k;
			}
		}
		return step;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
